DP 杂题泛做

T1

Description

给一个数列,长度为 10510^5 。划成 2020 段,每段权值为 #{i,jai=aj}\{i,j|a_i=a_j\}。要求最小化权值和。

Solution

阅读全文 »

HNOI2016 解题报告

T1 大数

Description

给定一个长度为 nn 的十进制数 s 和一个质数 ppqq 次询问,每次给定 l rl\ r ,询问有多少十进制数 s[x:y] (lxyr)(l\leq x\leq y\leq r) 能被 pp 整除。
1n,q2×105,p2×1091\leq n,q\leq 2\times 10^5,p\leq 2\times 10^9

阅读全文 »

SPOJ3734 Periodni

Description

给定一个 nn 列的表格,每列的高度 hih_i 各不相同,但底部对齐,然后向表格中填入 kk 个相同的数,填写时要求不能有两个数在同一列。若两个数在同一行,但是中间某一列断开是被允许的,否则也不允许。求填数的方案数对 109+710^9+7 取模的值。
n500,hi106n\leq 500,h_i\leq 10^6

Solution

阅读全文 »

HNOI2015 解题报告

T1 菜肴制作

Description

nn 道菜和有 mm 条要求,每条要求形如“A 号菜需要在 B 号菜的前面”。现在要求给出一个上菜序列,在满足所有要求的前提下,满足:

CF932G Palindrome Partition

Description

给定一个串,把串分成偶数段,假设为 s1,s2,,sks_1,s_2,\cdots,s_k ,要求满足 s1=sk,s2=sk1,s_1=s_k,s_2=s_{k-1},\cdots ,求方案数。
n105n\leq 10^5

Solution

阅读全文 »

一类树形 dp 方程的可换根化处理

换根 dp 是一个广为流传的算法。
换根 dp 对于 dp 方程是有要求的,一般而言 dp 方程中只能含有常数和与 i 的子树有关的项。
本文将探讨对于下述方程如何使其可以换根处理

f[p]=(ewe×f[son])+deppf[p]=(\sum_{e} w_e\times f[son])+\text{dep}_p

阅读全文 »

Luogu4299 首都

Description

nn 个点,初始时互不连通。有 qq 次操作,分别为如下三种类型:

Quiz 0107 Summary

T1 word

Description

你有一个由小写字母组成的长度为 nn 的字符串。每一步你要找到它的子串中最短的重复块(一个重复块由一个字符串与自身连接而成)。如果有多于一个,你必须选择最左边的那个。你要将那个形如 XX(X - 某个字符串)的重复块替换成 X,即删除其中的一个 X。重复以上步骤直到字符串中不存在重复块。
输出最终的字符串。

阅读全文 »